package leetcode_1801_1900;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

public class LeeCode_1834 {
    public static void main(String[] args) {
        System.out.println(Arrays.toString(getOrder(new int[][]{{1, 2}, {2, 4}, {3, 2}, {4, 1}})));
//        System.out.println(Arrays.toString(getOrder(new int[][]{{7,10},{7,12},{7,5},{7,4},{7,2}})));
    }
    private static int[] getOrder(int[][] tasks) {
        int n = tasks.length;
        int[][] nts = new int[n][3];
        for (int i = 0; i < n; i++) {
            nts[i] = new int[]{tasks[i][0], tasks[i][1], i};
        }
        Arrays.sort(nts, Comparator.comparingInt(o -> o[0]));
        PriorityQueue<int[]> q = new PriorityQueue<>((o1, o2) -> {
            if (o1[1] != o2[1]){
                return o1[1] - o2[1];
            }
            return o1[2] - o2[2];
        });
        int[] ans = new int[n];
        for (int time = 1, j = 0, idx = 0;idx < n;){
            while (j < n && nts[j][0] <= time){
                q.add(nts[j++]);
            }
            if (q.isEmpty()){
                time = nts[idx][0];
            }else {
                int[] poll = q.poll();
                ans[idx++] = poll[2];
                time += poll[1];
            }
        }
        return ans;
    }
}
